CS 5010: Problem Set 7

Out: Monday, October 27, 2014

Due: Monday, November 3, 2014 at 600pm.

The goal of this problem set is to give you additional practice using general recursion and invariants.

Remember that you must follow the design recipe.

For each function that you write using general recursion, you must be prepared to identify:

• which are the trivial cases
• for each non-trivial case, where and how you divided the problem into sub-problems.
• for each non-trivial case, how you built the solution to the original problem from the solutions to the subproblems.
• for each non-trivial case, whether or not it recurs on a substructure of one of the arguments.

Remember that every function that uses general recursion must have either a halting measure (if it always halts) or a comment that it sometimes does not halt (with an example).

(I don't believe there are any functions on this problem set that should sometimes fail to terminate).

Also, if you really need to do so, it is ok for a function using general recursion to call itself via a help function. If so, you need make sure that your halting measure decreases on EVERY recursive call to the function, even if that call comes via a help function.

As before, if your function does not fulfill its purpose for all combinations of arguments that satisfy the contract, then you must write an invariant that documents what additional assumptions your function makes about its arguments.

If you have two values of compound type, you may decompose both of them at once. For example, you may write something like

STRATEGY: structural decomposition on Ball
(define (some-fn b1 b2)
  (some-code (ball-x b1) (ball-y b1) (ball-x b2) (ball-y b2)))

You don't need to write a separate template for this. The structs need not be of the same type.

Write a paragraph or two near the top of your file, explaining your approach and what you did so that the TA will be able to understand your algorithm BEFORE READING ANY OF THE CODE. You may also wish to write such introductions to major sections of your file.

You must use DrScheme's HtDP Intermediate Student Language with Lambda. You should not need to require any libraries besides rackunit, "extras.rkt", and "sets.rkt." Use refactoring to avoid duplication whenever it is helpful. Use list abstractions like filter, fold, and map whenever they are helpful. As in past problems, you will be penalized if you fail to see clear occasions for their use.

As usual, the rubric for` grading is here. You should also refer to the more detailed guidelines here.

1. Imagine an infinite chessboard. The board begins at (1,1) and streaches out infinitely in two directions. You can think of the positions on the board as pairs of positive integers.

   We say that two positions on the board are adjacent iff they share a corner, but not an edge. So positions (1,2) and (2,3) are adjacent, and so are (1,2) and (2,1), but positions (1,2) and (1,3) are not adjacent because they share an edge. (See the power of examples!). We say a position p is adjacent to some set of positions S iff it is adjacent to some position q in S.

   The board also contains some blocks. Each block sits at exactly one position on the chessboard, and completely fills that position. Here's a picture of a board with blocks on positions (1,2),(1,3),(2,3),(3,2),(3,4),(4,1),(4,4).

   

   Here we've represented the positions using computer-graphics coordinates, so all the positions with x = 1 are in the first column.

   A position that contains a block is said to be occupied; otherwise it is vacant.

   A set of positions is an obstacle iff it has the following properties:

   1. The set is non-empty
   2. Every position in the set is occupied
   3. Any two positions in the set are linked by a chain of adjacent blocks in the set.
   4. Every position that is adjacent to any position in the set is either in the set or is vacant.

   Clearly each occupied position on the chessboard is part of a unique obstacle. There are 3 obstacles in the picture: {(1,2),(2,3),(3,2),(4,1),(3,4)}, {(1,3)}, and {(4,4)}.

   The problem is: given the list of the positions on the board that contain blocks, to find the obstacles on the board

   You will have to select suitable data structures and algorithms, in addition to designing the functions. For example, you may or may not choose to represent the board as a list of blocks.

   The API below uses the following data definitions:

   ;; A Position is a (list PosInt PosInt)
   ;; (x y) represents the position x, y.
   ;; Note: this is not to be confused with the built-in data type Posn.
   
   ;; A PositionSet is a list of positions without duplication.
   
   ;; A PositionSetSet is a list of PositionSets without duplication,
   ;; that is, no two position-sets denote the same set of positions.
   

   For example, (list (list 1 2) (list 1 3)) and (list (list 1 3) (list 1 2)) are both PositionSets, but

   (list
     (list (list 1 2) (list 1 3))
     (list (list 1 3) (list 1 2)))
   

   is NOT a PositionSetSet, because both of these position sets denote the same set of positions, namely {(1,2),(1,3)}.

   Write a file "obstacles.rkt" that provides the following functions

   position-set-equal? : PositionSet PositionSet -> Boolean
   GIVEN: two PositionSets
   RETURNS: true iff they denote the same set of positions.
   
   obstacle? : PositionSet -> Boolean
   GIVEN: a PositionSet
   RETURNS: true iff the set of positions would be an obstacle if they
   were all occupied and all other positions were vacant.
   
   blocks-to-obstacles : PositionSet -> PositionSetSet
   GIVEN: the set of occupied positions on some chessboard
   RETURNS: the set of obstacles on that chessboard.
   

   Before you turn in your solution, make sure it passes the tests in ps07-obstacles-qualification.rkt. As before, download this file, save it in your set07 directory, and run it to qualify your program for grading. Be sure to commit this file to repository so we know that you've done this correctly.

   For what it's worth, my solution to this problem was 103 lines + tests, and the median time-on-task reported by students the last time I assigned this problem was about 10 hours.

2. Let's go back to that chessboard. On the chessboard, we have a robot and some blocks. The robot occupies a single square on the chessboard, as do the blocks. The robot can move any number of squares north, east, south, or west.

   You are to write a file called robot.rkt that provides the following function:

   path : Position Position ListOf<Position> -> Maybe<Plan>>
   GIVEN:
   1. the starting position of the robot,
   2. the target position that robot is supposed to reach
   3. A list of the blocks on the board
   RETURNS: a plan that, when executed, will take the robot from
   the starting position to the target position without passing over any
   of the blocks, or false if no such sequence of moves exists.
   
   This API uses the following data definitions:
   
   ;; A Position is a (list PosInt PosInt)
   ;; (x y) represents the position at position x, y.
   ;; Note: this is not to be confused with the built-in data type Posn.
   
   ;; A Move is a (list Direction PosInt)
   ;; Interp: a move of the specified number of steps in the indicated
   ;; direction. 
   
   ;; A Direction is one of
   ;; -- "north"
   ;; -- "east"
   ;; -- "south"
   ;; -- "west"
   
   ;; A Plan is a ListOf<Move>
   ;; WHERE: the list does not contain two consecutive moves in the same
   ;; direction. 
   

   Before you turn in your solution, make sure it passes the tests in ps07-robot-qualification.rkt. As before, download this file, save it in your set07 directory, and run it to qualify your program for grading. Be sure to commit this file to repository so we know that you've done this correctly.